#include<iostream>
#include<vector>
using namespace std;

//记忆化搜索04：猜数字大小II
class Solution4 {
public:
    //vector<vector<int>> memo;
    int memo[202][202];
    //size_t ret=-1;
    int getMoneyAmount(int n) 
    {
        return dfs(1,n);
    }

    int dfs(int first,int last)
    {
        if(last<=first)
        {
            //memo[first][last]=0;
            return 0;
        }
        // if(last-first==1)
        // {
        //     memo[first][last]=first;
        //     return first;
        // }
        if(memo[first][last]!=0)   return memo[first][last];
        int ret=INT_MAX;
        
        for(int i=first;i<=last;i++)
        {
            int tmp=max(dfs(first,i-1),dfs(i+1,last))+i;
            if(ret>tmp) ret=tmp;
        }
        memo[first][last]=ret;
        return ret;    
    }
};

//记忆化搜索05：矩阵中的最长递增路劲
class Solution5 {
public:
    //vector<vector<int>> memo;
    int memo[201][201];
    int dx[4]={0,0,-1,1};
    int dy[4]={-1,1,0,0};
    int m;
    int n;
    int longestIncreasingPath(vector<vector<int>>& matrix) 
    {
        m=matrix.size();
        n=matrix[0].size();
        int ret=1;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                int tmp=dfs(matrix,i,j);
                if(ret<tmp) ret=tmp;
            }            
        }
        return ret;  
    }
    int dfs(vector<vector<int>>& matrix,int i,int j)
    {
        if(memo[i][j]!=0)   return memo[i][j];

        int ret=1;

        for(int k=0;k<4;k++)
        {
            int x=dx[k]+i;
            int y=dy[k]+j;
            if(x>=0&&x<m&&y>=0&&y<n&&matrix[x][y]>matrix[i][j])
            {
                int tmp=dfs(matrix,x,y)+1;
                ret=ret<tmp?tmp:ret;
            }                
        }
        memo[i][j]=ret;
        return ret;
    }
};




int main()
{
    return 0;   
}